<!DOCTYPE html>

<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <title>扁平的数据结构转成树形结构</title>
    </head>
    <body>
        <script>
            let arr = [
                { id: 1, name: '部门1', pid: 0 },
                { id: 2, name: '部门2', pid: 1 },
                { id: 3, name: '部门3', pid: 1 },
                { id: 4, name: '部门4', pid: 3 },
                { id: 5, name: '部门5', pid: 4 }
            ];
            const getChildren = (arr, result, pid) => {
                arr.forEach((item, index) => {
                    if (item.pid == pid) {
                        const newItem = {
                            ...item,
                            children: []
                        };
                        result.push(newItem);
                        getChildren(arr, newItem.children, newItem.id);
                    }
                });
            };
            //递归实现
            const arrayToTree = (data, pid) => {
                let result = [];
                getChildren(data, result, pid);
                return result;
            };
            //console.log(arrayToTree(arr,0))


            //非递归的方式实现
            function arrayToTree2(items) {
                const result = []; // 存放结果集
                const itemMap = {}; //

                // 先转成map存储
                //for (const item of items) {
                    //itemMap[item.id] = { ...item, children: [] };
                //}
                console.log(itemMap)
                for (const item of items) {
                    const id = item.id;
                    const pid = item.pid;
                    if (!itemMap[id]) {
                      itemMap[id] = {
                        children: [],
                      }
                    }
                    itemMap[id] = {
                      ...item,
                      children: itemMap[id]['children'] //保存之前已有的数据(引用的问题)
                    }

                    const treeItem = itemMap[id];
                    if (pid === 0) {
                        result.push(treeItem);
                    } else {
                        if (!itemMap[pid]) {
                            itemMap[pid] = {
                                children: []
                            };
                        }
                        itemMap[pid].children.push(treeItem); //因为是引用的问题，所以会修改原数据，因此result的值就是最终的结果了(引用传递)
                    }
                }
                return result;
            }
            console.log(arrayToTree2(arr));
        </script>
    </body>
</html>
